#include <vector>
class Solution {
public:
   
    int longestPalindromeSubSeq(string s) {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<n;j++){
                if(i>j) dp[i][j]=0;
                else if(i==j) dp[i][j]=1;
                else {
                    if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                    else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
};



class Solution2 {
  public:

    int longestPalindromeSubSeq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {

                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }

}
;